package service.impl;

import model.VirtualMemory;
import service.ReplaceService;

import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.List;

/**
 * Created by PanD
 */

public class ReplaceServiceImpl implements ReplaceService {

    @Override
    public Double replaceWithFIFO(List<VirtualMemory> instructionList, int sizeOfMemory) {
        List<VirtualMemory> memoryList = new ArrayList<>();
        Double pageMissing = new Double(0);
        for (VirtualMemory page : instructionList
             ) {
            //检查是否发生缺页
            if (!memoryList.contains(page)) {
                // 检查页框是否有空位,空闲则直接添加
                if (memoryList.size() < sizeOfMemory) {
                    memoryList.add(page);
                } else {
                    pageMissing++;  //缺页数+1
                    memoryList.remove(0);
                    memoryList.add(page);
                }
            }
        }
        return (new BigDecimal(1-pageMissing/instructionList.size()))
                .setScale(4, BigDecimal.ROUND_HALF_UP).doubleValue();
    }

    @Override
    public Double replaceWithOPT(List<VirtualMemory> instructionList, int sizeOfMemory) {
        List<VirtualMemory> memoryList = new ArrayList<>();
        Double pageMissing = new Double(0);
        for (VirtualMemory page : instructionList
        ) {
            //检查是否发生缺页
            if (!memoryList.contains(page)) {
                // 检查页框是否有空位,空闲则直接添加
                if (memoryList.size() < sizeOfMemory) {
                    memoryList.add(page);
                } else {
                    pageMissing++;  //缺页数+1
                    //哨兵，复制当前内存页面，用于向后检查
                    List<VirtualMemory> checker = getCopyList(memoryList);
                    //获取目前索引
                    int currentIndex = instructionList.indexOf(page);
                    //通过哨兵向后查找确定最长时间未使用的页面
                    for (int i = currentIndex+1; i < instructionList.size(); i++) {
                        if (checker.contains(instructionList.get(i))) {
                            checker.remove(instructionList.get(i));
                        }
                        //确定最长时间未使用的页面
                        if (checker.size() == 1) {
                            break;
                        }
                    }
                    //去除最长时间未使用页，加入新页面
                    memoryList.set(memoryList.indexOf(checker.get(0)), page);
                }
            }
        }

        return (new BigDecimal(1-pageMissing/instructionList.size()))
                .setScale(4, BigDecimal.ROUND_HALF_UP).doubleValue();
    }

    @Override
    public Double replaceWithLRU(List<VirtualMemory> instructionList, int sizeOfMemory) {
        List<VirtualMemory> memoryList = new ArrayList<>();
        Double pageMissing = new Double(0);
        for (VirtualMemory page : instructionList
        ) {
            //检查是否发生缺页
            if (!memoryList.contains(page)) {
                // 检查页框是否有空位,空闲则直接添加
                if (memoryList.size() < sizeOfMemory) {
                    memoryList.add(page);
                } else {
                    pageMissing++;  //缺页数+1
                    //哨兵，复制当前内存页面，用于向前检查
                    List<VirtualMemory> checker = getCopyList(memoryList);
                    //获取目前索引
                    int currentIndex = instructionList.indexOf(page);
                    //通过哨兵向前查找确定最长时间未使用的页面
                    for (int i = currentIndex-1; i >= 0; i--) {
                        if (checker.contains(instructionList.get(i))) {
                            checker.remove(instructionList.get(i));
                        }
                        //确定最长时间未使用的页面
                        if (checker.size() == 1) {
                            break;
                        }
                    }
                    //去除最长时间未使用页，加入新页面
                    memoryList.set(memoryList.indexOf(checker.get(0)), page);
                }
            }
        }
        return (new BigDecimal(1-pageMissing/instructionList.size()))
                .setScale(4, BigDecimal.ROUND_HALF_UP).doubleValue();
    }

    //复制List（当前物理内存容量），作为哨兵查找
    private List<VirtualMemory> getCopyList(List<VirtualMemory> sourceList) {
        List<VirtualMemory> desList = new ArrayList<>();
        for (VirtualMemory v :
                sourceList) {
            desList.add(v);
        }
        return desList;
    }
}
